package com.datastructure.test.gasstation;

public class GasStation {

    public static void main(String[] args) {
        GasStation gasStation = new GasStation();
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        int station = gasStation.gasStation(gas, cost);
        System.out.println(station);
    }

    public int gasStation (int[] gas, int[] cost) {
        // write code here
        if(gas==null||gas.length==0||cost==null||cost.length==0){
            return -1;
        }
        int length = gas.length;
        int index = 0;
        ListNode gasListNode = constructListNode(gas);
        ListNode costListNode = constructListNode(cost);
        while (index<length){
            if(gasListNode.val<costListNode.val){
                gasListNode=gasListNode.next;
                costListNode=costListNode.next;
                index++;
                continue;
            }
            int result = computeGasStation(gasListNode,costListNode,length);
            if(result!=-1){
                return index;
            }
            gasListNode=gasListNode.next;
            costListNode=costListNode.next;
            index++;
        }
        return -1;
    }

    private int computeGasStation(ListNode gasListNode, ListNode costListNode,int length) {
        int num = 0;
        int sumOfGas = 0;
        while (true){
            if(length==num){
                return 1;
            }
            if(sumOfGas<0){
                return -1;
            }
            sumOfGas+= gasListNode.val;
            sumOfGas-= costListNode.val;
            gasListNode=gasListNode.next;
            costListNode=costListNode.next;
            num++;
        }
    }

    public ListNode constructListNode(int[] data){
        if(data==null||data.length==0){
            return null;
        }
        ListNode cur;
        ListNode gasListNode = null;
        ListNode head = null;
        boolean isFirst = true;
        for (int i = data.length - 1; i >= 0; i--) {
            cur = new ListNode(data[i]);
            if(isFirst){
                head=cur;
                isFirst=false;
            }
            cur.next = gasListNode;
            gasListNode=cur;
        }
        head.next=gasListNode;
        return gasListNode;
    }
}
class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
}